home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / gs24src.zip / GSMISC.C < prev    next >
C/C++ Source or Header  |  1992-03-21  |  11KB  |  357 lines
  1. /* Copyright (C) 1989, 1992 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gsmisc.c */
  21. /* Miscellaneous utilities for Ghostscript library */
  22. #include "gx.h"
  23. #include "malloc_.h"
  24. #include "memory_.h"
  25.  
  26. /* Ghostscript writes to gs_out instead of stdout, */
  27. /* and writes debugging output to gs_debug_out. */
  28. FILE *gs_out;
  29. /* We define gs_debug and gs_debug_out even if DEBUG isn't defined, */
  30. /* so that we can compile individual modules with DEBUG set. */
  31. char gs_debug[128];
  32. FILE *gs_debug_out;
  33. /* We define gs_log_errors here for the same reason. */
  34. int gs_log_errors = 0;
  35.  
  36. /* We can turn on allocator debugging even if DEBUG isn't defined. */
  37. int gs_alloc_debug = 0;
  38. byte gs_alloc_fill_alloc = 0xa1;
  39. byte gs_alloc_fill_free = 0xf1;
  40.  
  41. /* A handy table for counting 1-bits. */
  42. const byte count_bits_table[256] = {
  43.     0, 1, 1, 2, 1, 2, 2, 3,   1, 2, 2, 3, 2, 3, 3, 4,
  44.     1, 2, 2, 3, 2, 3, 3, 4,   2, 3, 3, 4, 3, 4, 4, 5,
  45.     1, 2, 2, 3, 2, 3, 3, 4,   2, 3, 3, 4, 3, 4, 4, 5,
  46.     2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6,
  47.     1, 2, 2, 3, 2, 3, 3, 4,   2, 3, 3, 4, 3, 4, 4, 5,
  48.     2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6,
  49.     2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6,
  50.     3, 4, 4, 5, 4, 5, 5, 6,   4, 5, 5, 6, 5, 6, 6, 7,
  51.     1, 2, 2, 3, 2, 3, 3, 4,   2, 3, 3, 4, 3, 4, 4, 5,
  52.     2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6,
  53.     2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6,
  54.     3, 4, 4, 5, 4, 5, 5, 6,   4, 5, 5, 6, 5, 6, 6, 7,
  55.     2, 3, 3, 4, 3, 4, 4, 5,   3, 4, 4, 5, 4, 5, 5, 6,
  56.     3, 4, 4, 5, 4, 5, 5, 6,   4, 5, 5, 6, 5, 6, 6, 7,
  57.     3, 4, 4, 5, 4, 5, 5, 6,   4, 5, 5, 6, 5, 6, 6, 7,
  58.     4, 5, 5, 6, 5, 6, 6, 7,   5, 6, 6, 7, 6, 7, 7, 8
  59. };
  60.  
  61. /* Generate a block of unique IDs. */
  62. static ulong gs_next_id = 0;
  63. ulong
  64. gs_next_ids(uint count)
  65. {    ulong id;
  66.     if ( gs_next_id == 0 ) gs_next_id++;
  67.     id = gs_next_id;
  68.     gs_next_id += count;
  69.     return id;
  70. }
  71.  
  72. /* Versions of malloc and free compatible with Ghostscript's */
  73. /* model of memory management.  We keep track of all allocated */
  74. /* blocks so we can free them at cleanup time. */
  75. /* We must make sure that malloc_blocks leave the block aligned. */
  76. typedef struct malloc_block_s malloc_block;
  77. #define malloc_block_data\
  78.     malloc_block *next;\
  79.     uint size;\
  80.     const char *cname
  81. struct malloc_block_data_s { malloc_block_data; };
  82. struct malloc_block_s {
  83.     malloc_block_data;
  84.     byte _pad[-sizeof(struct malloc_block_data_s) & 7];    /* pad to double */
  85. };
  86. private malloc_block *malloc_list = 0;
  87. char *
  88. gs_malloc(uint num_elts, uint elt_size, const char *client_name)
  89. {    char *ptr;
  90.     uint size;
  91.     if ( num_elts > (max_uint - sizeof(malloc_block)) / elt_size )
  92.        {    /* Can't represent the size in a uint! */
  93.         lprintf3("%s: malloc(%u,%u) too large for size_t\n",
  94.              client_name, num_elts, elt_size);
  95.         return 0;
  96.        }
  97.     size = num_elts * elt_size;
  98.     ptr = malloc(size + sizeof(malloc_block));
  99.     if ( ptr == 0 )
  100.        {    if ( gs_alloc_debug )
  101.             lprintf3("%s: malloc(%u,%u) failed\n",
  102.                  client_name, num_elts, elt_size);
  103.        }
  104.     else
  105.        {    malloc_block *bp = (malloc_block *)ptr;
  106.         bp->next = malloc_list;
  107.         bp->size = size;
  108.         bp->cname = client_name;
  109.         malloc_list = bp;
  110.         ptr = (char *)(bp + 1);
  111. #ifdef DEBUG
  112. if ( gs_debug['A'] | gs_debug['a'] )
  113.         dprintf3("[a+]%lx:%u (%s)\n",
  114.              (ulong)ptr, bp->size, client_name);
  115. #endif
  116.         if ( gs_alloc_debug )
  117.           { /* Clear the block in an attempt to track down */
  118.             /* uninitialized data errors. */
  119.             memset(ptr, gs_alloc_fill_alloc, size);
  120.           }
  121.        }
  122.     return ptr;
  123. }
  124. void
  125. gs_free(char *ptr, uint num_elts, uint elt_size, const char *client_name)
  126. {    malloc_block *bp = malloc_list;
  127. #ifdef DEBUG
  128. if ( gs_debug['A'] | gs_debug['a'] )
  129.     dprintf2("[a-]%lx:%u\n", (ulong)ptr, num_elts * elt_size);
  130. #endif
  131.     if ( ptr == (char *)(bp + 1) )
  132.       {
  133. #ifdef DEBUG
  134.         if ( bp->size != num_elts * elt_size )
  135.           lprintf5("%s: free 0x%lx(%u,%u) size ~= %u\n",
  136.                client_name, (ulong)ptr, num_elts, elt_size,
  137.                bp->size);
  138. #endif
  139.         malloc_list = bp->next;
  140.         if ( gs_alloc_debug )
  141.           memset((char *)(bp + 1), gs_alloc_fill_free, bp->size);
  142.         free(bp);
  143.       }
  144.     else
  145.       { malloc_block *np;
  146.         for ( ; (np = bp->next) != 0; bp = np )
  147.           { if ( ptr == (char *)(np + 1) )
  148.           {
  149. #ifdef DEBUG
  150.             if ( np->size != num_elts * elt_size )
  151.               lprintf5("%s: free 0x%lx(%u,%u) size ~= %u\n",
  152.                    client_name, (ulong)ptr, num_elts, elt_size,
  153.                    np->size);
  154. #endif
  155.             bp->next = np->next;
  156.             if ( gs_alloc_debug )
  157.               memset((char *)(np + 1), gs_alloc_fill_free, np->size);
  158.             free(np);
  159.             return;
  160.           }
  161.           }
  162.         lprintf4("%s: free 0x%lx(%u,%u) not found\n",
  163.              client_name, (ulong)ptr, num_elts, elt_size);
  164.         free((char *)((malloc_block *)ptr - 1));
  165.       }
  166. }
  167. void
  168. gs_malloc_release()
  169. {    malloc_block *bp = malloc_list;
  170.     malloc_block *np;
  171.     for ( ; bp != 0; bp = np )
  172.        {    np = bp->next;
  173.         if ( gs_alloc_debug )
  174.           memset((char *)(bp + 1), gs_alloc_fill_free, bp->size);
  175.         free(bp);
  176.        }
  177.     malloc_list = 0;
  178. }
  179.  
  180. /* Swap even and odd bytes. */
  181. /* This routine may be supplanted by assembly code. */
  182. #if !USE_ASM
  183. #undef memswab                /* see memory_.h */
  184. void
  185. memswab(const char *src, char *dest, int count)
  186. {    register const uint *sptr = (uint *)src;
  187.     register uint *dptr = (uint *)dest;
  188.     register int x;
  189.     register uint w;
  190.     for ( x = count >> 3; --x >= 0; )
  191.        {    w = *sptr;
  192. #if arch_ints_are_short
  193.         *dptr = (w >> 8) + (w << 8);
  194.         w = sptr[1];
  195.         dptr[1] = (w >> 8) + (w << 8);
  196.         w = sptr[2];
  197.         dptr[2] = (w >> 8) + (w << 8);
  198.         w = sptr[3];
  199.         dptr[3] = (w >> 8) + (w << 8);
  200.         sptr += 4, dptr += 4;
  201. #else
  202.         *dptr = ((w << 8) & 0xff00ff00) + ((w >> 8) & 0x00ff00ff);
  203.         w = sptr[1];
  204.         dptr[1] = ((w << 8) & 0xff00ff00) + ((w >> 8) & 0x00ff00ff);
  205.         sptr += 2, dptr += 2;
  206. #endif
  207.        }
  208.     switch ( count & 6 )
  209.        {
  210.     case 6:
  211.         w = ((ushort *)sptr)[2];
  212.         ((ushort *)dptr)[2] = (w >> 8) + (w << 8);
  213.     case 4:
  214.         w = ((ushort *)sptr)[1];
  215.         ((ushort *)dptr)[1] = (w >> 8) + (w << 8);
  216.     case 2:
  217.         w = ((ushort *)sptr)[0];
  218.         ((ushort *)dptr)[0] = (w >> 8) + (w << 8);
  219.     case 0:
  220.         ;
  221.        }
  222. }
  223. #endif                    /* !USE_ASM */
  224.  
  225. /* Transpose an 8 x 8 block of bits.  line_size is the raster of */
  226. /* the input data.  dist is the distance between output bytes. */
  227. /* This routine may be supplanted by assembly code. */
  228. #if !USE_ASM
  229.  
  230. #if 1        /* This is the better of the two algorithms. */
  231.  
  232. void
  233. memflip8x8(const byte *inp, int line_size, byte *outp, int dist)
  234. {    register uint ae, bf, cg, dh;
  235.        {    const byte *ptr4 = inp + (line_size << 2);
  236.         ae = ((uint)*inp << 8) + *ptr4;
  237.         inp += line_size, ptr4 += line_size;
  238.         bf = ((uint)*inp << 8) + *ptr4;
  239.         inp += line_size, ptr4 += line_size;
  240.         cg = ((uint)*inp << 8) + *ptr4;
  241.         inp += line_size, ptr4 += line_size;
  242.         dh = ((uint)*inp << 8) + *ptr4;
  243.        }
  244.  
  245.     /* Check for all 8 bytes being the same. */
  246.     /* This is especially worth doing for the case where all are zero. */
  247.     if ( ae == bf && ae == cg && ae == dh && (ae >> 8) == (ae & 0xff) )
  248.        {    if ( ae == 0 ) goto store;
  249.         *outp = -((ae >> 7) & 1);
  250.         outp += dist;
  251.         *outp = -((ae >> 6) & 1);
  252.         outp += dist;
  253.         *outp = -((ae >> 5) & 1);
  254.         outp += dist;
  255.         *outp = -((ae >> 4) & 1);
  256.         outp += dist;
  257.         *outp = -((ae >> 3) & 1);
  258.         outp += dist;
  259.         *outp = -((ae >> 2) & 1);
  260.         outp += dist;
  261.         *outp = -((ae >> 1) & 1);
  262.         outp += dist;
  263.         *outp = -(ae & 1);
  264.         return;
  265.        }
  266.  
  267.        {    register uint temp;
  268.  
  269. /* Transpose a block of bits between registers. */
  270. #define transpose(r,s,mask,shift)\
  271.   r ^= (temp = ((s >> shift) ^ r) & mask);\
  272.   s ^= temp << shift
  273.  
  274. /* Transpose blocks of 4 x 4 */
  275. #define transpose4(r) transpose(r,r,0x00f0,4)
  276.     transpose4(ae);
  277.     transpose4(bf);
  278.     transpose4(cg);
  279.     transpose4(dh);
  280.  
  281. /* Transpose blocks of 2 x 2 */
  282.     transpose(ae, cg, 0x3333, 2);
  283.     transpose(bf, dh, 0x3333, 2);
  284.  
  285. /* Transpose blocks of 1 x 1 */
  286.     transpose(ae, bf, 0x5555, 1);
  287.     transpose(cg, dh, 0x5555, 1);
  288.  
  289.        }
  290.  
  291. store:    *outp = ae >> 8;
  292.     outp += dist;
  293.     *outp = bf >> 8;
  294.     outp += dist;
  295.     *outp = cg >> 8;
  296.     outp += dist;
  297.     *outp = dh >> 8;
  298.     outp += dist;
  299.     *outp = (byte)ae;
  300.     outp += dist;
  301.     *outp = (byte)bf;
  302.     outp += dist;
  303.     *outp = (byte)cg;
  304.     outp += dist;
  305.     *outp = (byte)dh;
  306. }
  307.  
  308. #else        /* This looked like a good idea, but it's no faster. */
  309.  
  310. /* Transpose an 8 x 8 block of bits.  line_size is the raster of */
  311. /* the input data.  dist is the distance between output bytes. */
  312. void
  313. memflip8x8(const byte *inp, int line_size, byte *outp, int dist)
  314. {    /* Define a table that spreads the bits of its index as follows: */
  315.     /* 0->0-3, 1->8-11, 2->16-19, 3->24-27, */
  316.     /* 4->4-7, 5->12-15, 6->20-23, 7->28-31. */
  317. #define b4(v) v,v+0xf,v+0xf00,v+0xf0f
  318. #define b8(v) b4(v),b4(v+0xf0000)
  319. #define b16(v) b8(v),b8(v+0xf000000)
  320.     static const ulong spread[256] =
  321.      { b16(0), b16(0xf0), b16(0xf000), b16(0xf0f0),
  322.        b16(0xf00000), b16(0xf000f0), b16(0xf0f000), b16(0xf0f0f0),
  323.        b16(0xf0000000), b16(0xf00000f0), b16(0xf000f000), b16(0xf000f0f0),
  324.        b16(0xf0f00000), b16(0xf0f000f0), b16(0xf0f0f000), b16(0xf0f0f0f0)
  325.      };
  326.     register ulong hi, lo, temp;
  327.     hi = spread[*inp] & 0x88888888;
  328.     inp += line_size;
  329.     hi |= spread[*inp] & 0x44444444;
  330.     inp += line_size;
  331.     hi |= spread[*inp] & 0x22222222;
  332.     inp += line_size;
  333.     hi |= spread[*inp] & 0x11111111;
  334.     inp += line_size;
  335.     lo = spread[*inp] & 0x88888888;
  336.     inp += line_size;
  337.     lo |= spread[*inp] & 0x44444444;
  338.     inp += line_size;
  339.     lo |= spread[*inp] & 0x22222222;
  340.     inp += line_size;
  341.     lo |= spread[*inp] & 0x11111111;
  342.     temp = (hi & 0xf0f0f0f0) | ((lo >> 4) & 0x0f0f0f0f);
  343.     *outp = (byte)((uint)(temp >> 16) >> 8); outp += dist;
  344.     *outp = (byte)(temp >> 16); outp += dist;
  345.     *outp = (byte)((uint)temp >> 8); outp += dist;
  346.     *outp = (byte)(temp); outp += dist;
  347.     temp = ((hi << 4) & 0xf0f0f0f0) | (lo & 0x0f0f0f0f);
  348.     *outp = (byte)((uint)(temp >> 16) >> 8); outp += dist;
  349.     *outp = (byte)(temp >> 16); outp += dist;
  350.     *outp = (byte)((uint)temp >> 8); outp += dist;
  351.     *outp = (byte)(temp);
  352. }
  353.  
  354. #endif        /* memflip8x8 */
  355.  
  356. #endif                    /* !USE_ASM */
  357.